package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-10-01 13:20
 */

import java.util.HashMap;

/**
 * 题目：给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。
 * 如果 s 中存在多个符合条件的子字符串，返回任意一个。
 * <p>
 * 示例：输入：s = "ADOBECODEBANC", t = "ABC"
 * 输出："BANC"
 * 解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'
 */
public class Test30_含有所有字符的最短字符串 {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> map1 = new HashMap<>();
        HashMap<Character, Integer> map2 = new HashMap<>();
        int len = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        int cout = 0;
        int min = 0;
        for (int i = 0; i < t.length(); i++) {
            map1.put(t.charAt(i), map1.getOrDefault(t.charAt(i), 0) + 1);
        }
        while (right < s.length()) {
            char a = s.charAt(right);
            right++;
            if (map1.containsKey(a)) {
                map2.put(a, map2.getOrDefault(a, 0) + 1);
                if (map2.get(a).equals(map1.get(a))) {
                    cout++;
                }
            }
            while (cout == map1.size()) {
                if (right - left < len) {
                    min = left;
                    len = right - left;
                }
                char b = s.charAt(left);
                left++;
                if (map1.containsKey(b)) {
                    if (map1.get(b).equals(map2.get(b))) {
                        cout--;
                    }
                    map2.put(b, map2.getOrDefault(b, 0) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(min, min + len);
    }
}
